package main

import "go-leetcode/leetcode/utils"

// 108. 将有序数组转换为二叉搜索树
func main() {
	array := []int{-10, -3, 0, 5, 9}

	toBST := utils.SortedArrayToBST(array)
	utils.PrintTreeNode(toBST)
}

func sortedArrayToBST(nums []int) *utils.TreeNode {
	// 中序遍历，放成有序数组
	// 往回转换，可以转换成很多个二叉树，但是题目需要平衡二叉树，所以直接切中点
	if len(nums) == 0 {
		return nil
	}
	if len(nums) == 1 {
		return &utils.TreeNode{
			Val: nums[0],
		}
	}

	numLen := len(nums)
	mid := numLen / 2

	currValue := nums[mid]
	root := &utils.TreeNode{
		Val:   currValue,
		Left:  sortedArrayToBST(nums[:mid]),
		Right: sortedArrayToBST(nums[mid+1:]),
	}

	return root
}

// 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵
//平衡
// 二叉搜索树。
//
//示例 1：
//
//输入：nums = [-10,-3,0,5,9]
//输出：[0,-3,9,-10,null,5]
//解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
//
//示例 2：
//
//输入：nums = [1,3]
//输出：[3,1]
//解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
//
//提示：
//
//1 <= nums.length <= 104
//-104 <= nums[i] <= 104
//nums 按 严格递增 顺序排列
